#include <stdio.h>
#include <stdlib.h>

typedef int ElemSet; /* 默认元素为整数*/
typedef struct RecordNode {
    ElemSet key; /* 关键字 */
    /* 其他属性由用户自定义 */
} Records;

typedef Records *TElemSet;
typedef struct BinaryTreeNode *Position; /* 树结点指针是元素的位置 */
typedef struct BinaryTreeNode *BinaryTree;
struct BinaryTreeNode {
    TElemSet data; /* 数据元素 */
    BinaryTree left; /* 左孩子指针 */
    BinaryTree right; /* 右孩子指针 */
};
#define NIL NULL

/* 算法11-4 二叉查找树的查找 SearchBST(bstree, key) */
Position SearchBST(BinaryTree bstree, ElemSet key) {
    Position ret;

    ret = NIL; /* 初始化为查找不成功的返回值NIL */
    if (bstree != NIL) {
        if (key < bstree->data->key) {
            ret = SearchBST(bstree->left, key);
        } else if (key > bstree->data->key) {
            ret = SearchBST(bstree->right, key);
        } else { /* key = bstree.data.key */
            ret = bstree;
        }
    }
    return ret;
}
/* 算法11-4 结束 */

/* 算法11-5 二叉查找树的插入 InsertBST(bstree, x) */
BinaryTree InsertBST(BinaryTree bstree, TElemSet x) {
    if (bstree == NIL) { /* 若是空树 */
        bstree = (BinaryTree)malloc(sizeof(struct BinaryTreeNode));
        bstree->data = x;
        bstree->left = bstree->right = NIL;
    } else { /* 若不是空树 */
        if (x->key < bstree->data->key) {
            bstree->left = InsertBST(bstree->left, x);
        } else if (x->key > bstree->data->key) {
            bstree->right = InsertBST(bstree->right, x);
        } /* x.key = bstree.data.key 时不重复插入 */
    }
    return bstree;
}
/* 算法11-5 结束 */

/* 算法11-6 二叉查找树的删除 DeleteBST(bstree, key) */
BinaryTree DeleteBST(BinaryTree bstree, ElemSet key) {
    BinaryTree t;

    if (bstree == NIL) { /* 若是空树 */
        printf("错误：%d不在树中。\n", key);
    } else { /* 若不是空树 */
        if (key < bstree->data->key) {
            bstree->left = DeleteBST(bstree->left, key);
        } else if (key > bstree->data->key) {
            bstree->right = DeleteBST(bstree->right, key);
        } else { /* key = bstree.data.key 找到了，删除之 */
            if (bstree->left != NIL && bstree->right != NIL) { /* 左右子树都有 */
                t = bstree->left; /* t用于寻找中序遍历中bstree的直接前驱 */
                while (t->right != NIL) {
                    t = t->right;
                }
                bstree->data = t->data; /* 用前驱的数据替换bstree的数据 */
                bstree->left = DeleteBST(bstree->left,
                                         t->data->key); /* 从左子树中删掉t */
            } else { /* 至多只有一棵子树 */
                t = bstree;
                if (bstree->left == NIL) {
                    bstree = bstree->right;
                } else if (bstree->right == NIL) {
                    bstree = bstree->left;
                } /* 此时bstree指向唯一子树，或NIL */
                free(t); /* 释放删除的结点空间 */
            }
        }
    }
    return bstree;
}
/* 算法11-6 结束 */

int main(void) {
    TElemSet x;
    BinaryTree bstree;
    int n, i;
    ElemSet key;
    Position p;

    bstree = NIL;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        x = (TElemSet)malloc(sizeof(Records));
        scanf("%d", &x->key);
        bstree = InsertBST(bstree, x);
    }
    scanf("%d", &key);
    p = SearchBST(bstree, key);
    if (p != NIL) {
        printf("Found key = %d\n", p->data->key);
    } else {
        printf("NotFound.\n");
    }
    bstree = DeleteBST(bstree, key);
    p = SearchBST(bstree, key);
    if (p != NIL) {
        printf("Found key = %d\n", p->data->key);
    } else {
        printf("NotFound.\n");
    }

    return 0;
}